class SortAlgorithm:
    @staticmethod
    def shell_sort(arr):
        """希尔排序实现，记录每一步操作（臧程志）"""
        steps = []
        n = len(arr)
        gap = n // 2
        
        while gap > 0:
            for i in range(gap, n):
                temp = arr[i]
                j = i
                while j >= gap and arr[j - gap] > temp:
                    arr[j] = arr[j - gap]
                    j -= gap
                    # 记录交换操作
                    steps.append(f"交换位置 {j} 和 {j+gap}")
                arr[j] = temp
                # 记录当前数组状态
                steps.append(f"当前数组: {arr}")
            gap //= 2
        
        return arr, steps

    @staticmethod
    def insertion_sort(arr):
        """插入排序算法（黄浩轩）"""
        steps = []
        # 遍历数组，从第二个元素开始
        for i in range(1, len(arr)):
            # 将当前元素赋值给key
            key = arr[i]
            # 将当前元素的前一个元素赋值给j
            j = i - 1
            # 当j大于等于0且key小于arr[j]时，将arr[j]赋值给arr[j+1]，并将j减1
            while j >= 0 and key < arr[j]:
                arr[j + 1] = arr[j]
                j -= 1
                # 记录交换操作
                steps.append(f"将 {arr[j+1]} 移动到位置 {j+2}")
            # 将key赋值给arr[j+1]
            arr[j + 1] = key
            # 记录当前数组状态
            steps.append(f"当前数组: {arr}")
        # 返回排序后的数组和步骤
        return arr, steps

    @staticmethod
    def quick_sort(arr):
        """快速排序算法（邓惠铭）"""
        steps = []
        arr = arr.copy()  # 创建副本避免修改原数组
        
        def _partition(low, high):
            """分区函数"""
            pivot = arr[high]  # 选择最后一个元素作为基准值
            steps.append(f"选择基准值 {pivot} (位置 {high})")
            i = low - 1  # 小于基准值的元素索引
        
            for j in range(low, high):
                if arr[j] <= pivot:
                    i += 1
                    if i != j:  # 仅在不同位置时交换
                        arr[i], arr[j] = arr[j], arr[i]
                        steps.append(f"交换 {arr[j]} 和 {arr[i]} (位置 {i} ↔ {j})")
                        steps.append(f"当前数组：{arr}")
        
            # 将基准值放到正确位置
            arr[i+1], arr[high] = arr[high], arr[i+1]
            steps.append(f"基准值 {pivot} 归位到位置 {i+1}")
            steps.append(f"分区后数组：{arr}")
            return i + 1

        def _sort(low, high):
            """递归排序函数"""
            if low < high:
                steps.append(f"\n处理子数组：{arr[low:high+1]} (位置 {low}-{high})")
                pi = _partition(low, high)
                _sort(low, pi-1)
                _sort(pi+1, high)
    
        steps.append(f"初始数组：{arr}")
        _sort(0, len(arr)-1)
        steps.append(f"\n最终结果：{arr}")
        return arr, steps

    @staticmethod
    def bubble_sort(arr):
        """冒泡排序算法（李兴业）"""
        steps = []
        n = len(arr)
        # 遍历数组
        for i in range(n):
            # 标记是否有交换操作
            swapped = False
            # 内层循环，每次将未排序部分的最大值冒泡到末尾
            for j in range(0, n-i-1):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swapped = True
                    # 记录交换操作
                    steps.append(f"交换 {arr[j+1]} 和 {arr[j]} (位置 {j+1} ↔ {j})")
                    steps.append(f"当前数组: {arr}")
            # 如果没有交换操作，说明数组已经有序
            if not swapped:
                break
        # 记录最终结果
        steps.append(f"最终结果：{arr}")
        return arr, steps

    @staticmethod
    def save_log(algorithm_name, result, execution_time, steps=None):
        """保存排序结果日志和步骤"""
        import os
        import json
        import time
        
        log_dir = "./data/logs"
        if not os.path.exists(log_dir):
            os.makedirs(log_dir)
            
        log_file = os.path.join(log_dir, f"{algorithm_name}_result.json")
        log_data = {
            "algorithm": algorithm_name,
            "timestamp": time.strftime("%Y-%m-%d %H:%M:%S"),
            "execution_time": execution_time,
            "result": result,
            "steps": steps if steps else "No steps recorded"
        }
        
        with open(log_file, "w") as f:
            json.dump(log_data, f, indent=4)

